package 单链表;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.List;

public class Main {
    public ListNode insertionSortList(ListNode head) {
        if (head == null) {
            return head;
        }
        ListNode dummy = new ListNode(0);
        dummy.next = head;
        ListNode last = head, cur = head.next;
        while (cur != null) {
            if (last.val <= cur.val) {
                last = last.next;
            } else {
                ListNode pre = dummy;
                while (pre.next.val <= cur.val) {
                    pre = pre.next;
                }
                last.next = cur.next;
                cur.next = pre.next;
                pre.next = cur;
            }
            cur = last.next;
        }
        return dummy.next;
    }

    //两两交换链表中的节点
    public ListNode swapPairs(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }
        ListNode dummy = new ListNode(0);
        dummy.next = head;
        ListNode pre = dummy;
        while (pre.next != null && pre.next.next != null) {
            ListNode first = pre.next;
            ListNode second = first.next;
            pre.next = second;
            first.next = second.next;
            second.next = first;
            pre = first;
        }
        return dummy.next;
    }

    // 合并区间
    public int[][] merge(int[][] intervals) {
        if (intervals.length == 0) {
            return intervals;
        }
        List<int[]> list = new ArrayList<>();
        // 进行排序
        Arrays.sort(intervals, (a, b) -> a[0] - b[0]);
        list.add(intervals[0]);
        for (int i = 1; i < intervals.length; i++) {
            int[] cur = intervals[i];
            int[] last = list.get(list.size() - 1);
            if (cur[0] <= last[1]) {
                // cur[0是当前的区间的左边界 last是已经拍好的最后区间右边界
                // 更新last的又边界
                last[1] = Math.max(last[1], cur[1]);
            } else {
                list.add(cur);
            }
        }
        return list.toArray(new int[list.size()][]);
    }

    public ListNode removeNthFromEnd(ListNode head, int n) {
        //删除单链表的倒数第n个节点
        //  1-2-3-4-5-6-7-8-9-10->null
        //  n=2
        //  dummy->1-2-3-4-5-6-7-8-9-10->null
        if (head == null) {
            return null;
        }
        ListNode dummy = new ListNode(0); //使用虚拟头节点解决删除头节点的情况
        dummy.next = head;

        ListNode fast = dummy;
        for (int i = 0; i < n; i++) {
            fast = fast.next;
        }
        ListNode slow = dummy;

        while (fast.next != null) {
            fast = fast.next;
            slow = slow.next;
        }

        slow.next = slow.next.next;
        return dummy.next;
    }
   //https://leetcode.cn/problems/add-two-numbers/description/
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        ListNode p = l1, q = l2;
        ListNode dummy = new ListNode(0);
        ListNode curr = dummy;
        int carry = 0;
        while (p != null || q != null) {
            // 如果不为空 那么就是等于原来的节点值 如果没空就等于0
            int x = p != null ? p.val : 0;
            int y = q != null ? q.val : 0;
            int sum = x + y + carry;
            //carry是用来进位的
            carry = sum / 10;
            ListNode newNode = new ListNode(sum % 10);
            curr.next = newNode;
            curr = curr.next;
            //如果不为空那么再往后移动 为空了就不用再移动了
            if (p != null) p = p.next;
            if (q != null) q = q.next;
        }
        //最后还需要进一位
        if (carry == 1) {
            ListNode node = new ListNode(carry);
            curr.next = node;
        }
        return dummy.next;
    }
}
